package solution.liuyu2783.offer;

/**
 * 剑指 Offer 03. 数组中重复的数字
 *
 */
public class Q03_DuplicateNum_E {
	
	 /**
     * 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
     * Input:
     * {2, 3, 1, 0, 2, 5}
     *
     * Output:
     * 2
     */
    public int duplicate(int numbers[], int length) {
        int result = -1;
        if(numbers == null || length <= 0)
            return result;

        for(int i = 0; i < length; i++) {
            while(i != numbers[i]) {
                if(numbers[i] ==  numbers[numbers[i]]) {
                    result = numbers[i];
                    return result;
                }
                swap(numbers, i, numbers[i]);
            }
        }
        return result;
    }

    public void swap(int arr[], int i, int j) {
        int temp = 0;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        Q03_DuplicateNum_E duplicateNum = new Q03_DuplicateNum_E();
        int[] nums = new int[]{2, 3, 1, 0, 2, 5};
        System.out.println(duplicateNum.duplicate(nums, nums.length));
    }
}
